Title

Similar Question

Solution Tips

方案一: 构造图 + DFS

var numIslands = function(grid) {
    // 第一次遍历先构建图
    const graph = new Graph();

    // 永远取左边和上边做构建边, 所以可以直接从 1,1 开始遍历
    // 可以增加一个前导0行, 这样保证第一行的节点都可以正确初始化
    grid.unshift(Array.from({ length: grid[0].length }, () => "0"));
    for (let i = 1; i < grid.length; i++) {
        const row = grid[i];
        for (let j = 0; j < row.length; j++) {
            if (grid[i][j] === "1" ) {
                const vertex = [i, j].join(',');
                graph.addVertex(vertex)
                if (grid[i - 1][j] === "1") {
                    graph.addEdge([i - 1, j].join(','), vertex)
                }
                if (grid[i][j - 1] === "1") {
                    graph.addEdge([i, j - 1].join(','), vertex)
                }
            }
        }
    }

    // 然后再次遍历图, 每次队列清空了就是一个单独的岛
    // bfs
    const map = graph.adjList;
    const queue = [];
    let count = 0;
        for (const [key, val] of map) {
        if (queue.length === 0) {
            if (val) {
                queue.push([key, val]);
                count++;
            }
        }

        while (queue.length) {
            // 这个 shift 实在是太慢了, bfs 超时...
            const [vertex, adjList] = queue.shift();

            for (let i = 0; i < adjList.length; i++) {
                map.get(adjList[i]) && queue.push([adjList[i], map.get(adjList[i])]);
            }
            // 处理完该节点后, 置空
            map.set(vertex, null)
        }
    }

    return count;
    // 如果是 dfs
};

方案二: 直接基于网格进行遍历

Dfs

var numIslands = function(grid) {
    // 增加填充行, 参考的是 dummyHead 的逻辑
    const startRow = Array.from({length: grid[0].length}, () => '0');
    const endRow = Array.from({length: grid[0].length}, () => '0');
    grid.unshift(startRow);
    grid.push(endRow);

    let count = 0;
    // 直接从第一行开始遍历即可
    for (let i = 1; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === '1') {
                count++;
                dfs(i, j);
            }
        }
    }

    function dfs(r, c) {
        // if (!inArea(grid, r, c)) return;
        if (grid[r][c] !== '1') return;

        // 已经遍历过的岛屿标记为 2
        grid[r][c] = '2';

        // 继续递归四个方向
        dfs(r - 1, c);
        dfs(r + 1, c);
        dfs(r, c + 1);
        dfs(r, c - 1);
    }

    return count;
};

Bfs

var numIslands = function(grid) {
    // 增加填充行, 参考的是 dummyHead 的逻辑
    const startRow = Array.from({length: grid[0].length}, () => '0');
    const endRow = Array.from({length: grid[0].length}, () => '0');
    grid.unshift(startRow);
    grid.push(endRow);

    let count = 0;
    // 直接从第一行开始遍历即可
    for (let i = 1; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === '1') {
                count++;
                bfs(i, j);
            }
        }
    }

    function bfs(r, c) {
        // bfs 逻辑也是和二叉树类似的 queue
        const queue = [[r, c]];

        while (queue.length) {
            const vertex = queue.shift();
            const [r, c] = vertex;

            if (grid[r][c] === '1') {
                // 标记已经遍历过, 避免重复
                grid[r][c] = '2';
                // 继续遍历四个方向
                queue.push([r + 1, c]);
                queue.push([r - 1, c]);
                queue.push([r, c + 1]);
                queue.push([r, c - 1]);

            }
        }
    }

    return count;
};

方案三: 并查集